﻿#include "unit_test.h"
#include <stack>
#include <deque>
#include <cassert>

namespace code_01_03
{
    int GetLastAndRemove(std::stack<int>& s)
    {
        assert(!s.empty());
        int top = s.top();
        s.pop();
        if (s.empty())
        {
            return top; // 最后一个，返回，s长度会减1
        }
        else
        {
            int last = GetLastAndRemove(s);
            s.push(top);    // 再次插入，保持顺序不变
            return last;
        }
    }

    /**
     * 逆转stack
     * 思路：想办法把stack中的值保存到运行时栈中，再倒序插入
     */
    void Reverse(std::stack<int>& s)
    {
        if (s.size() > 1)
        {
            int last = GetLastAndRemove(s); // 取出最底下的元素
            Reverse(s);                     // 剩下部分原地逆序
            s.push(last);                   // 最底下的元素最后插入，实现逆序
        }
    }

    TEST(ReverseStack)
    {
        std::stack<int> s({ 1, 2, 3 });
        Reverse(s);
        std::stack<int> expected({ 3, 2, 1 });
        ASSERT_EQ(true, s == expected);
    }
}
